import java.util.Arrays;

public class Solution {

    public static void main(String[] args) {
        Solution s = new Solution();
        // 测试：边界测试复合要求
        System.out.println(s.getPermutation(3, 3));
    }

    public String getPermutation(int n, int k) {
        /**
         * 排列序列
         * 解法：
         *  使用回溯算法解决全排列问题*/
        int[] factorial = calculateFactorial(n);
        boolean[] used = new boolean[n + 1];
        Arrays.fill(used, false);
        StringBuilder path = new StringBuilder();
        dfs(0, n, k, path, used, factorial);
        return path.toString();
    }

    private void dfs(int index, int n, int k, StringBuilder path, boolean[] used, int[] factorial) {
        /**
         * 回溯本体*/
        if (index == n) {
            return;
        }
        // 计算还未确定的数字的全排列的个数，第 1 次进入的时候是 n - 1
        int count = factorial[n - 1 - index];
        for (int i = 1; i <= n; i++) {
            if (used[i]) {
                continue;
            }
            if (count < k) {
                k -= count;
                continue;
            }
            path.append(i);
            used[i] = true;
            dfs(index + 1, n, k, path, used, factorial);
            return;
        }
    }

    private int[] calculateFactorial(int n) {
        /**
         * 计算阶乘*/
        int[] factorial = new int[n + 1];
        factorial[0] = 1;
        for (int i = 1; i <= n; i++) {
            factorial[i] = factorial[i - 1] * i;
        }
        return factorial;
    }

}
